package lc;

import java.util.ArrayList;


public class Ex1095_2 {

static class MountainArray extends ArrayList<Integer> {
    public static int length() {
        return 0;
    }
}
    
class Solution {
    public int findInMountainArray(int target, MountainArray mountainArr) {
        int n = MountainArray.length(), m = -1, mid, lo = 0, hi = n - 1;
        int a, b;
        while (lo <= hi) {
            mid = (hi - lo) / 2 + lo;
            if ((a = mountainArr.get(mid)) > (b = mountainArr.get(mid - 1)) && a < mountainArr.get(mid + 1)) {
                m = mid;
                break;
            } else if (b < mountainArr.get(mid + 1)) {
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }

        lo = 0;
        hi = m;

        while (lo < hi) {
            mid = (hi - lo) / 2 + lo;
            if (mountainArr.get(mid) < target) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }

        if (mountainArr.get(lo) == target) {
            return lo;
        }

        lo = m + 1;
        hi = n - 1;

        while (lo < hi) {
            mid = (hi - lo) / 2 + lo;
            if (mountainArr.get(mid) > target) {
                hi = mid - 1;
            } else {
                lo = mid;
            }
        }

        return mountainArr.get(lo) == target ? lo : -1;
    }
}
}
